/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  //存放所有节点值
  const result = []

  function preDfs(root) {
    //递归边界
    if (!root) {
      result.push('#')
      return
    }
    //把当前节点值存入数组result，再递归处理左、右子树
    result.push(root.val)
    preDfs(root.left)
    preDfs(root.right)
  }
  preDfs(root)

  return result.join(',')
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const nodes = data.split(',')
  //当前处理的节点索引
  let index = 0

  function buildTree() {
    //递归边界（所有节点构建完毕 或 碰到叶子节点）
    if (index >= nodes.length || nodes[index] === '#') {
      index++
      return null
    }

    //创建当前节点，并递归构建左、右子树
    const node = new TreeNode(parseInt(nodes[index++]))
    node.left = buildTree()
    node.right = buildTree()

    //返回当前构建完毕的节点
    return node
  }
  const root = buildTree()

  return root
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */